package demo17;

import demo16.Tree44;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

public class Tree45 {
    static class TreeNode45 {
        public char val;
        public TreeNode45 left;
        public TreeNode45 right;

        public TreeNode45(char val) {
            this.val = val;
        }
    }
    public TreeNode45 create4() {
        TreeNode45 head = new TreeNode45('1');
        TreeNode45 head2 = new TreeNode45('2');
        TreeNode45 head3 = new TreeNode45('3');
        TreeNode45 head4 = new TreeNode45('4');
        TreeNode45 head5 = new TreeNode45('5');
        TreeNode45 head6 = new TreeNode45('6');
        head.left = head2;
        head.right = head3;
        head2.left = head4;
        head2.right = head5;
        head3.left = head6;
        return head;
    }
    //根据前序遍历和中序遍历构建二叉树
    public  int preindex=0;
    public TreeNode45 bulidTree(String pre,String ord){

        return bulidTreeChild(pre,ord,0,ord.length()-1);
    }
    public TreeNode45 bulidTreeChild(String pre, String ord,int begin,int end){
        if(begin>end){
            System.out.println("树为空!!!");
            return null;
        }

       TreeNode45 root = new TreeNode45(pre.charAt(preindex));
        int rootIndex=find(ord,begin,end,pre.charAt(preindex));
        preindex++;
        root.left=bulidTreeChild(pre,ord,begin,rootIndex-1);
        root.right=bulidTreeChild(pre,ord,rootIndex+1,end);
        System.out.println(root.val);
        return root;
    }
    //打印
    private int find(String ord,int begin,int end,char val){
        for(int i=begin;i<=end;i++){
            if(ord.charAt(i)==val){
                return i;
            }
        }
        return -1;
    }
    public void levelorder(TreeNode45 head) {
        if(head==null){
            System.out.println("树为空！！");
            return;
        }
        TreeNode45 cur=head;
        Queue<TreeNode45> q=new LinkedList();
        q.offer(cur);
        while(!q.isEmpty()){
            TreeNode45 cur1=q.poll();//弹出队中元素并打印
            System.out.print(cur1.val+" ");
            if(cur1.left!=null){ //节点左右不为空左右存入队里
                q.offer(cur1.left);
            }
            if(cur1.right!=null){
                q.offer(cur1.right);
            }
        }
    }
    //二叉树创建字符串:左子树存在左节点不为null就添加左括号递归处理完左树就加右括号，左子树不存在右树存在需要用（）占位，右树不存在，啥也不拼
    //右子树只存在用（递归处理完右子树再添加），若无右子树，不用拼括号
    public String tree(TreeNode45 root){
        if(root==null){
            return null;
        }
        StringBuilder stringBuilder=new StringBuilder();
        treechild(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void treechild(TreeNode45 root,StringBuilder stringBuilder){
        if(root==null){
            return;
        }
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append("(");
            treechild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right==null){
                return;
            }else{
                    stringBuilder.append("()");
                }
            }
            if(root.right!=null){
                stringBuilder.append("(");
                treechild(root.right,stringBuilder);
                stringBuilder.append(")");
            }else{
                return;
            }
        }
        //前序遍历的非递归实现：利用栈存储节点，控制遍历的顺序，一路向左访问并存储根节点，左子树遍历后回溯处理右子

    public void pre(TreeNode45 head){
        TreeNode45 cur=head;
        if(cur==null){
            return;
        }
        Stack<TreeNode45> s=new Stack<>();
        while(!s.isEmpty()||cur!=null){
            while (cur!=null){
                s.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode45 top=s.pop();
            cur=top.right;
        }
    }
    //非递归式实现中序遍历
    public void inorder(TreeNode45 head){
        TreeNode45 cur=head;
        if(cur==null){
            return;
        }
        Stack<TreeNode45> s=new Stack<>();
        while (!s.isEmpty()||cur!=null){
            while(cur!=null) {
                s.push(cur);
                cur=cur.left;
            }
            TreeNode45 Top=s.pop();
            System.out.print(Top.val+" ");
            cur=Top.right;
        }
    }
    }

